package com.it.base.arithmetic.tree.tree.binaryTree;

import com.it.base.arithmetic.tree.entity.Node;

/**
 * 二叉树的基本操作
 */
public class OpsTree implements Tree {
    private Node root;
    public OpsTree(Node root)  {
        this.root = root;
    }

    /**
     * 查找某个节点，我们必须从根节点开始遍历。
     *
     * 　　①、查找值比当前节点值大，则搜索右子树；
     *
     * 　　②、查找值等于当前节点值，停止搜索（终止条件）；
     *
     * 　　③、查找值小于当前节点值，则搜索左子树；
     * @param node
     * @return
     */
    @Override
    public Node find(Node node) {
        Node current = root;
        if(current==null){
            System.out.printf("树为空，无法遍历");
        }
        while (current!=null){
            //当前需要查找的节点比遍历的节点值大，则需要在找右边的节点
            if(node.getKey()>current.getKey()){
                current = current.getRightNode();
            }
            //当前需要查询的值比当前遍历的值小的情况，需要向左查找
            else  if(node.getKey()< current.getKey()){
                current=current.getLeftNode();
            }
            else {

                return current;
            }

        }

        return null;
    }

    @Override
    public boolean insert(Node node) {
        //如果传进来的是空，直接添加失败
        if(node==null){
            return false;
        }
        //如果现在树是空，则直接等于
        if(this.root==null){
            this.root=node;
            return true;
        }else{
            //如果树不为空，需要遍历，找到对应的位置
            Node current = this.root;
            while (current!=null){
                //待插入节点大于当前节点
                 if(node.getKey()>current.getKey()){
                     //当前节点的子节点为空，则直接可以插入
                     if(current.getRightNode()==null){
                         current.setRightNode(node);
                         return true;
                     }else{
                         //待插入节点比当前节点的右节点小，则需要在当前节点和当前节点的右几点中间新增一个节点，把待插入的数据插入到这个位置
                       if(node.getKey()<current.getRightNode().getKey()){
                             node.setRightNode(current.getRightNode());
                             current.setRightNode(node);
                             return true;
                         }else{
                             current = current.getRightNode();
                         }
                     }


                 }
                 //待插入节点小于当前节点
                 else if(node.getKey()<current.getKey()){
                     //如果当前节点的左节点为空，则直接插入到左节点
                     if(current.getLeftNode()==null){
                         current.setLeftNode(node);
                         return true;
                     }else if(current.getLeftNode()!=null){
                         //如果待插入节点大于当前节点的左节点，则需要插入到当前节点和左节点中间，即新增一个节点到当前节点和当前节点的左节点中间
                         if(node.getKey()>current.getLeftNode().getKey()){
                             node.setLeftNode(current.getLeftNode());
                             current.setLeftNode(node);
                             return true;
                         }
                         else {
                             current =current.getLeftNode();
                         }
                     }


                 }

            }


        }


        return false;
    }

    @Override
    public boolean delete(Node node) {

        if (node==null){

            System.out.printf("待删除节点不能为空");
            return false;
        }
        if(this.root==null){
            System.out.printf("树不能为空");
            return false;
        }
        Node current = this.root;
        while (current!=null){
            //待删除节点大于当前节点，向右遍历
            if(node.getKey()>current.getKey()){
                current = current.getRightNode();
            }

            //待删除节点小于当前节点，向左遍历
            else if(node.getKey() <current.getKey()) {

                current=current.getLeftNode();
            }
            //找到待删除的节点
            else{
                System.out.printf("找到删除的节点了");
                if(current.getLeftNode()!=null){

                }

            }


        }




        return false;
    }



}
